package com.ai.zuochengyun.phase01.class01;

import java.util.*;

/**
 * 逆序对问题，右侧比左侧小，可以转换成归并思想求解
 */
public class Code07_InversePair {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 0, 4, 3, 1};
        System.out.println(test(arr));
        System.out.println(inversePair(arr));
    }

    private static List<String> test(int[] arr) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    ans.add(arr[i] + "," + arr[j]);
                }
            }
        }
        return ans;
    }

    private static List<String> inversePair(int[] arr) {
        if (arr == null || arr.length == 1) {
            return null;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static List<String> process(int[] arr, int left, int right) {
        if (left == right) {
            return new ArrayList<>();
        }
        List<String> ans = new ArrayList<>();
        int mid = left + ((right - left) >> 1);
        // 左侧的逆序对
        ans.addAll(process(arr, left, mid));
        // 右侧的逆序对
        ans.addAll(process(arr, mid + 1, right));
        // 合并的产生的逆序对
        ans.addAll(teacherMerge(arr, left, mid, right));
        return ans;
    }

    /**
     * 我自己的解法
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return
     */
    private static List<String> myMerge(int[] arr, int left, int mid, int right) {
        int size = right - left + 1;
        int[] help = new int[size];
        int index = 0;
        int p1 = left, p2 = mid + 1;
        List<String> ans = new ArrayList<>();

        // 左侧右侧都没有越界
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[index++] = arr[p1++];
            } else {
                for (int i = p1; i <= mid; i++) {
                    ans.add(arr[i] + "," + arr[p2]);
                }
                help[index++] = arr[p2++];
            }
        }
        // 左侧还有值
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        // 右侧还有值
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }

    /**
     * 导师的解法：从右往左merge，相等的时候，先拷贝右侧的
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return
     */
    private static List<String> teacherMerge(int[] arr, int left, int mid, int right) {
        int size = right - left + 1;
        int[] help = new int[size];
        int index = size - 1;
        // 从右往左merge
        int p1 = mid, p2 = right;
        List<String> ans = new ArrayList<>();

        // 左侧右侧都没有越界
        while (p1 >= left && p2 >= mid + 1) {
            // 左侧小于右侧不产生逆序对
            // 相等的时候，先拷贝右侧的
            if (arr[p1] <= arr[p2]) {
                help[index--] = arr[p2--];
            } else {
                // 左侧大于右侧的时候，拷贝左边的
                // p2 到 mid+1位置的数都小于当前值，可以拼逆序对
                for (int i = p2; i >= mid + 1; i--) {
                    ans.add(arr[p1] + "," + arr[i]);
                }
                help[index--] = arr[p1--];
            }
        }
        // 左侧还有值
        while (p1 >= left) {
            help[index--] = arr[p1--];
        }
        // 右侧还有值
        while (p2 >= mid + 1) {
            help[index--] = arr[p2--];
        }
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }
}
